package lc;

import util.ListNode;
import org.junit.*;
public class Ex25 {

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dommy = new ListNode(0);
        // dommy.next = head;
        ListNode next = head, tmp, result = dommy, end;
        while (true) {
            end = findEnd(k, next);
            if (end == null) {
                dommy.next = next;
                break;
            }
            tmp = end.next;
            end = reverse(next);
            dommy.next = end;
            dommy = next;
            next = tmp;
        }
        return result.next;
    }

    public ListNode findEnd(int k, ListNode head) {
        while (head != null) {
            head = head.next;
            k--;
            if (k == 1) {
                return head;
            }
        }
        return null;
    }

    public ListNode reverse(ListNode head) {
        ListNode pre = null, post = head, tmp;
        while (post != null) {
            tmp = post.next;
            post.next = pre;
            pre = post;
            post = tmp;
        }
        return pre;
    }

}

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1,2,3,4,5};
        ListNode head = ListNode.newListNodeFromArray(nums);
        System.out.println(s.reverseKGroup(head, 3));
    }

}
